CS267 Fall 2012Practice Final

To study for the final I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice final is below. Here are some facts about the actual final: (a) It is comprehensive (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) It is 10 problems, 6 problems will be on material since the midterm, four problems will come from the topics covered prior to the midterm. (f) Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm. (g) Answering the following three questions on the cover of the test (before you start the test) can be used to get one point back on any problem you miss: How long did you study for this test? Which topic did you spend the most time studying? What kinds of practice problems did you do in addition to those on the practice test to prepare?

1. Give a situation with numbers where it would make sense to rebuild an index rather than remerge.
2. Briefly explain (a) BM25F, (b) Pseudo-relevance feedback.
3. Explain how Dirichlet smoothing of language models works. What is the Language Modeling with Dirichlet smoothing relevance formula? Give an example using it.
4. What is document eliteness? How is it estimated in DFR? How is DFR modified to handled document-length normalization?
5. In terms of index partitioning, briefly explain how partition-by-term and partition-by-document can be done and how query processing is handled in each situation.
6. Distinguish intra-query and inter-query parallelism as far as information retrieval goes. What bottlenecks exists to intra-query parallelism if partition-by-document is used.
7. In calculating BM25 what components might need to be pre-computed before query time? Of these which components might benefit from being calculated using a map reduce algorithm. Pick one of these and give a map reduce algorithm for it.
8. Briefly describe the Traffic Rank linear optimization problem.
9. Explain how hub and authority scores are calculated in HITS.
10. Ignoring dangling nodes and the random jump factor give the mapper and reducer for a Map Reduce implementation of page rank.